HW#3 --- last modified February 17 2019 19:23:19..

Solution set.

Due date: Apr 6

Files to be submitted:
  Hw3.zip

Purpose: To practice the CFG, PDF, parsing algorithms learned in class as well as write down our first TMs.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO1 (Learning Outcome 1) -- Write a grammar for a language described otherwise.

LO7 -- Be able to use a pumping lemma to show that some languages are not regular and/or not context-free Use closure properties to simplify proofs of non-regularity of languages.

LO8 -- Be able to construct a pushdown automaton accepting a given language.

Specification:This homework will involve writing and coding. Put the problem write-up and any readme's for your code in Hw1.pdf, and bundle it with all JFLAP code files you create in Hw1.zip.

1. Give a context free grammar for palindromes (words spelt the same forwards and backwards) over the alphabet {a,b,c}. Implement this grammar in JFLAP. Show with screenshots and explanation going through the conversion process of this grammar to a PDA.
2. Consider the fragment of the following variation of HTML which involves paragraph tags, <p>, </p> ; bold face tags, <b>, </b>, and <i>, </i>. Ignore text that might appear within the tags. In this variant, it is legal to have multiple paragraphs within a document, but paragraph tags can't appear within paragraph tags. Bold and italic tags must appear within paragraph tags. Bold tags cannot appear within bold tags and italic tags cannot appear within italic tags. Give a context-free grammar for this language. Implement this grammar in JFLAP. Show screenshots with written explanation of going through the process of converting this grammar to Chomsky Normal Form in JFLAP.
3. Consider the document in the language of the last problem given by the string: "<p><b><i></i></b></p><p><b></b><i></i><b></b></p><p><i><b></b></i></p>". Using the CNF form of your grammar from the last problem in JFLAP step through the process of running the CYK algorithm on this string. Give screenshots and a brief description of what is happening at each step in your write-up. Since how JFLAP implements CYK is not particularly instructive, you may alternatively do this problem by hand.
4. Construct a PDA for the language L over {a,b,c} consisting of strings w in which every prefix of w has at least as many a's as c's. b's can occur anywhere in w. So for example, the empty string is in L, bab is in L, abbabbbcb is in L, but c, aacaccc are not. Implement this PDA in JFLAP. Show screenshots with written explanation of going through the process of converting this PDA to a context free grammar.
5. Prove using the pumping lemma the following languages are not context-free: (a) {0^f(n) | n ≥ 0 } where f is any function in Ω(n²), (b) {ww | w is a string over {a,b,c}}, (c) {0ⁿ#0⁴ⁿ#0⁸ⁿ | n ≥ 0}.
6. Pick your favorite family-oriented limerick. Make a table illustrating how the SEQUITUR algorithm would generate a small grammar for this limerick. Then using the encoding given in class show what the final compressed string for your limerick would be.

Point Breakdown